%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Stream Ciphers}
\label{StreamCiphers}

A stream cipher enciphers individual characters, usually bits,
of a plaintext message one at a time, with a cipher that varies
with time.  Block ciphers are {\em memoryless}, in the sense that
the same function is used to encipher successive blocks.
Stream ciphers, in contrast, must have memory.  As such they are
{\em state functions} because the current state $S_i$ of the function
is recorded in a memory buffer.  We saw how various modes of operation
(CFB, OFB) turn a memoryless block cipher into a state function by
feedback buffer.  A {\em keystream} is a sequence of characters
generated from the key and the current state, as input to the stream
cipher.

\section{Types of Stream Ciphers}

In a {\bf synchronous stream ciphers} the keystream is generated
independently of the plaintext message (or ciphertext).  Given a key
$K$, if the initial state is designated $S_0$, then, for each cycle
$i = 0,1,2,\dots$, the following equations describe the generation of
the keystream, ciphertext, and next state:
$$
\begin{array}{rr@{\ }c@{\ }l@{\ }l}
\hbox{\it Key stream function:} & k_i &=& g_K(S_i) \\
\hbox{\it Output function:} & c_i &=& h(k_i,m_i)   \\
\hbox{\it Next state function:} & S_{i+1} &=& f_K(S_i)
\end{array}
$$
An additive binary stream cipher is defined to be a synchronous
stream cipher in which $h = {\tt XOR}$.

A {\bf self-synchronizing} or {\bf asynchronous} stream cipher
is a stream cipher in which the keystream is a function of the key
and a fixed number of previous ciphertext characters.  Given a
key $K$ and initial state $S_0 = (c_{-t},\dots,c_{-1})$, the
keystream and ciphertext are generated for each cycle $i = 0,1,2,
\dots$ as for a synchronous stream cipher:
$$
\begin{array}{rr@{\ }c@{\ }l@{\ }}
\hbox{\it Key stream function:}\quad & k_i &=& g_K(S_i) \\
\hbox{\it Output function:}\quad & c_i &=& h(k_i,m_i)   \\
\end{array}
$$
with the next state set to $S_{i+1} = (c_{i+1-t},\dots,c_{i})$.

\section{Properties of Stream Ciphers}

\noindent{\bf Synchronous stream ciphers}
\begin{itemize}
\item
Synchronization: Sender and receiver are required to be synchronized
in terms of both state and key.
\item
Error propagation: None --- a bit error in the ciphertext affects
precisely one bit in the deciphered plaintext, provided that
synchronization is maintained.
\item
Attacks and features: Property (1) means that an active adversary
can use insertion, deletion, or replay of ciphertext; property (2)
implies that the affects of these changes effect direct changes on
the deciphered plaintext, which might be exploited.
\end{itemize}

\noindent{\bf Asynchronous stream ciphers}
\begin{itemize}
\item
Synchronization: An insertion, deletion, or change in ciphertext
characters results in loss of only a fixed number of deciphered
plaintext characters, after which the deciphering self-synchronizes.
\item
Error propagation: A ciphertext error in transmission affects at most
$t$ characters of the deciphered plaintext.
\item
Attacks and features: The error propagation makes active modification
more easily detected, while self-synchronization makes insertion,
deletion, or reply of ciphertext blocks more difficult to detect.
Since each plaintext character influences subsequent ciphertext, an
asynchronous stream cipher is better at masking plaintext structure
or redundancies.
\end{itemize}

%\begin{center}{\Large\bf MATH3024: Lecture 14}\end{center}

\section{Linear Feedback Shift Registers}

A linear feedback shift register implements a keystream function, and which
can be simply described by a schematic diagram of the following form:
$$
\SelectTips{cm}{10}
\xymatrix@R=6mm@C=3mm{
*+={} \ar@{-}[dd] & &
  *+={\oplus} \ar@{-}[ll] & &
  *+={\oplus} \ar@{->}[ll] &
  *+={} \ar@{->}[l] &
  *+={\oplus} \ar@{.}[l] & &
  *+={\oplus} \ar@{->}[ll] & &
  *+={} \ar@{->}[ll] \\
{} &
  *+[F]{\Rbox{$c_{1}$}} \ar@{->}[r] &
  *+={\otimes} \ar@{->}[u] &
  *+[F]{\Rbox{$c_{2}$}} \ar@{->}[r] &
  *+={\otimes} \ar@{->}[u] & & &
  *+[F]{\Rbox{$c_{n-1}$}} \ar@{->}[r] &
  *+={\otimes} \ar@{->}[u] &
  *+[F]{\Rbox{$c_{n}$}} \ar@{->}[r] &
  *+={\otimes} \ar@{-}[u] & \\
*+={} \ar@{->}[r] &
  *+[F]{\Rbox{$s_{n+i}$}} \ar@{-}[r] &
  *+={\cdot} \ar@{->}[r] \ar@{->}[u] &
  *+[F]{\Rbox{\vspace{2.5mm}}} \ar@{-}[r] &
  *+={\cdot} \ar@{->}[r] \ar@{->}[u] &
  *+={} \ar@{.}[r] &
  *+={} \ar@{->}[r] &
  *+[F]{\Rbox{$s_{i+2}$}} \ar@{-}[r] &
  *+={\cdot} \ar@{->}[r] \ar@{->}[u] &
  *+[F]{\Rbox{$s_{i+1}$}} \ar@{-}[r] &
  *+={\cdot} \ar@{-}[u] \ar@{->}[r] &
  s_i \dots s_1s_0\\
{} & R_{n-1} & & R_{n-2} & & *+={\hbox{\hspace{6mm}}}
  & \cdots & R_1 & & R_0 &
}
$$
Before discussing the mathematical definition of linear feedback
shift registers (LFSR's), we address the question ``Why?''.
A LFSR is essentially an elementary algorithm for generating
a keystream, which has the following desirable properties:
\begin{enumerate}
\item
Easy to implement in hardware.
\item
Produce sequences of long period.
\item
Produce sequences with good statistical properties.
\item
Can be readily analyzed using algebraic techniques.
\end{enumerate}

A LFSR is defined by $n$ {\em stages}, labelled $R_{n-1}, \dots,
R_1, R_0$, each storing one bit, and having one input and output,
and a timer which mark clock cycles $i = 0, 1, 2,\dots$.
At the $i$-th clock cycle:
\begin{enumerate}
\item
The contents of stage $0$ is output;
\item
The contents of $R_i$ moves to $R_{i-1}$, for $1\le i \le n-1$; and
\item
Stage $R_{n-1}$ is the bit sum of a prescribed subset of stages
$0,1,\dots,n-2$.
\end{enumerate}
We may denote the contents of stage $R_j$ at time $i$ by $s_{i+j}$,
and the algorithm for updating the contents of stage $R_{n-1}$ gives
a recurrence relation
$$
s_{n+i} = \sum_{j=0}^{n-1} c_{n-j} s_{i+j},
$$
where $c_j$, $1 \le j \le n$ are fixed bit constants specifying the
stages which contribute to the bit sum.  By setting $c_0 = 1$ we can
express the relation as $\sum_{j=0}^n c_{n-j} s_{i+j} = 0$.

We identify the constants $c_k$ with coefficients of a polynomial
$$
g(x) = \sum_{k=0}^n c_k x^k,
$$
which we call the {\em connection polynomial} of the LFSR.
Moreover, if can take the LFSR output bits $s_j$ as the coefficients
of a power series
$$
s(x) = \sum_{j=0}^\infty s_j x^j,
$$
then the recurrence relation expresses the fact that $s(x)g(x)$ is
a polynomial $f(x)$ of degree less than $n$.  In other words, the
power series takes the form $s(x) = f(x)/g(x)$.

\noindent{\bf Exercise.}
Verify that the equality $f(x) = s(x)g(x)$, for $f(x)$ a polynomial
of degree less than $n$, gives rise to the the stated recurrence for
the coefficients of $s(x)$.

The LFSR is said to be {\em nonsingular} if $c_n \ne 0$.  The
condition that $c_n = \cdots = c_{n-k} = 0$ gives rise to a LFSR in
which the feedback reduces to at most $n-k-1$ terms, hence, after
the initial $k$ bits are output, the LFSR sequence reduces to one
which can be modelled by a LFSR of length $n-k-1$.  For this reason
we hereafter make the assumption that the LFSR is nonsingular.

We note that since the next state of the shift register (i.e. the
contents of the collection of stages) depends only on the current
contents, and there are $2^n$ possible states, the output sequence
is eventually periodic.  Since the all zero initial state maps to
itself, it is clear that the maximal period for any LFSR of length
$n$ is $2^n-1$.  The connection polynomial is said to be
{\em primitive} if the period of the LFSR output sequence,
beginning at any nonzero state, is $2^n-1$.

We note that the output sequence has period $N$ if and only if
$(X^N+1)s(x)$ is a polynomial of degree at most $N-1$.  On the
other hand, since $s(x) = f(x)/g(x)$, if $f(x)$ and $g(x)$ have
no common factor, then it follows by the unique factorization
of polynomials that $g(x)$ divides $X^N+1$.  In particular, if
$g(x)$ is {\em irreducible}, since $\deg(f(x)) < \deg(g(x))$,
it follows that $f(x)$ and $g(x)$ have no common factors.
In summary, an irreducible connection polynomial of a LFSR must
divide $x^N+1$ where $N$ is the period of any nonzero output
sequence.

The theorem below shows that in fact every polynomial $g(x)$ in
$\F_2[x]$ with nonzero constant term must divides $X^N+1$ for some
$N$.  The special feature of irreducible connection polynomials,
and especially primitive polynomials, is that we will be able to
compute the value of $N$ and, for primitive polynomials, that it
is takes the the maximal possible value.

\begin{lemma}
If $g(x)$ is not divisible by $x$, then there exists a polynomial
$u(x)$ such that $x\,u(x) \bmod g(x) = 1$.
\end{lemma}

\noindent{\bf Proof.}
Since the constant term of $g(x)$ is 1, the polynomial $u(x) = (g(x)+1)/x$
satisfies $x\,u(x) = g(x) + 1$, from which the lemma follows. $\square$

\begin{theorem}
Every polynomial $g(x)$ in $\F_2[x]$ coprime to $x$ divides $x^N+1$
for some $N$.
\end{theorem}

\noindent{\bf Proof.}
Consider the sequence of remainders ${}\bmod g(x)$:
$$
1 \bmod g(x),\ x \bmod g(x),\ x^2 \bmod g(x),\ x^3 \bmod g(x),\dots
$$
Since every remainder is a unique polynomial of degree at most $n-1$,
there are at most $2^n$ distinct elements in this sequence.
It follows that there is some $N$ such that $x^i \bmod g(x)$ equals
$x^{N+i} \bmod g(x)$ for all sufficiently large $i$. Since $g(x)$
is not divisible by $x$, it follows from the previous lemma that
we can cancel the powers of $x^i$ to obtain $x^N \bmod g(x) = 1$.
We conclude that $x^N+1$ is divisible by $g(x)$.
$\square$

%\begin{center}{\Large\bf MATH3024: Lecture 15}\end{center}

\subsection*{Periods of LFSR's}

We begin with some theorems regarding LFSR's and their connection
polynomials.  First, we make or recall some standard definitions.
We define a polynomial $g(x)$ to be {\em irreducible} if the only
factorization $g(x) = h(x)k(x)$ is with $h(x)$ or $k(x)$ equal to
the constant polynomial.  We define the order of $x$ modulo $g(x)$
to be the smallest power $x^N$ of $x$ such that $x^N \bmod g(x)$
equals $1$.  A polynomial $g(x)$ is of degree $n$ is said to be
{\em primitive} if the order of $x$ modulo $g(x)$ is $2^n-1$.
The next theorem shows that the definition of primitive given in
the previous lecture agrees with the current one.

\begin{theorem}
The period of a sequence generated by a LFSR is independent of the
nonzero initial state if the connection polynomial is irreducible,
and the period takes the maximal value $2^n-1$ if and only if the
connection polynomial is primitive.
\end{theorem}

Since there are exactly $2^n-1$ possible nonzero states, it is
clear that a LFSR that produces an output sequence with this period
in fact cycles through all such states, so the period is independent
of the initial state.  As a consequence of the theorem, a primitive
polynomial is irreducible.  We now prove the theorem.

{\bf Proof.}
We first note that all possible $2^n-1$ output sequences are given
by the rational expressions $s(x) = f(x)/g(x)$, where $f(x)$ runs
through the all nonzero polynomials of degree less than the
connection polynomial $g(x)$.  If the $g(x)$ is irreducible, then
this expression is minimal --- $f(x)$ and $g(x)$ have no common
factors, so there is no cancellation.

Next we note that the minimal period $N$ of any power series $s(x)$
is the degree of the smallest $x^N+1$ for which $(x^N+1)s(x)$ is a
polynomial.  If also $s(x) = f(x)/g(x)$ is in minimal form, then
for any such $x^N+1$, the denominator $g(x)$ divides $x^N+1$.
If the connection polynomial $g(x)$ is irreducible, then the
denominator equals $g(x)$ independently of $s(x)$ and the initial
state which defines it, and so also is the period constant.

Finally the last statement follows by noting that $g(x)$ divides
$x^N+1$ if and only if $x^N \bmod g(x) = 1$.
$\square$

For cryptographic purposes, it is desirable to have sequences which
have very long period.  The advantage of LFSR's in this respect is
that the period grows exponentially in the length of the shift
register.  For small value of $n$, $2$, $3$, or $4$, the value of
the maximal possible period, $N = 2^n-1$, is still trivially small.
But as the table below shows, with modest values of $n$ we are able
to efficiently generate sequences with enormous period.

\begin{center}
\begin{minipage}[t]{25mm}
$
\begin{array}{rl}
 n & 2^n-1 \\
 1 &   1 \\
 2 &   3 \\
 3 &   7 \\
 4 &  15 \\
 5 &  31 \\
 6 &  63 \\
 7 & 127 \\
 8 & 255 \\
 9 & 511 \\
10 & 1023
\end{array}
$
\end{minipage}
\begin{minipage}[t]{35mm}
$
\begin{array}{rl}
 n & 2^n-1 \\
11 &   2047 \\
12 &   4095 \\
13 &   8191 \\
14 &  16383 \\
15 &  32767 \\
16 &  65535 \\
17 & 131071 \\
18 & 262143 \\
19 & 524287 \\
20 & 1048575
\end{array}
$
\end{minipage}
\begin{minipage}[t]{35mm}
$
\begin{array}{rl}
 n & 2^n-1 \\
21 &   2097151 \\
22 &   4194303 \\
23 &   8388607 \\
24 &  16777215 \\
25 &  33554431 \\
26 &  67108863 \\
27 & 134217727 \\
28 & 268435455 \\
29 & 536870911 \\
30 & 1073741823
\end{array}
$
\end{minipage}
\end{center}
As particular examples, the primitive trinomials such as
$x^{23}+x^5+1$, $x^{29}+x^2+1$, $x^{31}+x^3+1$, and $x^{41}+x^3+1$
define very efficiently computable recurrence relations for maximal
length LFSR's.

\section{Linear Complexity}

In addition to practical applications for generating pseudo-random
sequences, LFSR's are a useful theoretical tool for the characterization
of other binary sequences.  The {\em linear complexity} of a binary
sequence is a measure of the structure of the sequence -- a low linear
complexity implies a cryptographically weak sequence.

An infinite sequence $s=s_0,s_1,\dots$ is said to be generated by
a LFSR if it is the output sequence of the shift register for some
initial state.  The linear complexity $L(s)$ for an infinite sequence
$s$ is defined to be $0$ if $s$ is the all zero sequence, equal to
the minimum length of a LFSR which generates it if $s$ is periodic,
and equal to $\infty$ otherwise.
The linear complexity $L(s)$ of a finite sequence $s = s_0,s_1,\dots,
s_{n-1}$ is defined to be the minimum length of a shift register which
generates some sequence with initial segment $s$.  The {\em linear
complexity profile} of an infinite sequence $s$ is the sequence
$L_1(s), L_2(s),\dots$, where $L_i(s)$ is the linear complexity of
first $i$ terms of $s$.

\section*{Exercises}

\input{exercises/StreamCiphers}
